/* Kruskal.java */

import java.util.Arrays;
import java.util.Hashtable;

import graph.*;
import set.*;

/**
 * The Kruskal class contains the method minSpanTree(), which implements
 * Kruskal's algorithm for computing a minimum spanning tree of a graph.
 */

public class Kruskal {

	/**
	 * minSpanTree() computes the minimum spanning tree of g, and returns it as a new WUGraph.
	 * 
	 * The original WUGraph g is NOT changed.
	 * 
	 * @param g
	 *            the WUGraph we want to find the minimum spanning tree of
	 * @return a new WUGraph that is a spanning tree (all vertices connected),
	 *         with total weight less than or equal to the weight of every other spanning tree for g
	 */
	public static WUGraph minSpanTree(WUGraph g) {
		int i, j, len, r1, r2;
		Object v1, v2;

		/*
		 * Create a new graph T having the same vertices as G, but no edges
		 * (yet)
		 */
		int edgeCount = 0;
		int vertexCount = g.vertexCount();
		Object[] vertexList = g.getVertices();

		WUGraph T = new WUGraph();
		for (i = 0; i < vertexCount; i++) {
			T.addVertex(vertexList[i]);
		}

		/* Make a list (not necessarily linked) of all the edges in G. */
		Edge[] edgeList;
		Edge[] edgeListBig = new Edge[vertexCount * vertexCount];
		Neighbors n;
		for (i = 0; i < vertexCount; i++) {
			n = g.getNeighbors(vertexList[i]);
			len = n.neighborList.length;
			for (j = 0; j < len; j++) {
				edgeListBig[edgeCount] = new Edge(vertexList[i],
						n.neighborList[j], n.weightList[j]);
				edgeCount++;
			}
		}

		/* Trim array of edges (remove null values) */
		edgeList = new Edge[edgeCount];
		System.arraycopy(edgeListBig, 0, edgeList, 0, edgeList.length);

		/* Sort the edges by weight */
		Arrays.sort(edgeList);

		/* Finally, find the edges of T using disjoint sets */
		DisjointSets vertexSets = new DisjointSets(vertexCount);
		Hashtable<Integer, Integer> vertexTable = new Hashtable<Integer, Integer>();

		/* Vertex lookup table (vertex object hash code : array index) */
		for (i = 0; i < vertexCount; i++) {
			vertexTable.put(vertexList[i].hashCode(), i);
		}
		for (i = 0; i < edgeCount; i++) {
			v1 = edgeList[i].vertex1;
			v2 = edgeList[i].vertex2;
			r1 = vertexSets.find(vertexTable.get(v1.hashCode()));
			r2 = vertexSets.find(vertexTable.get(v2.hashCode()));
			if (r1 == r2) { /* Vertices already connected. Do nothing */
			} else {
				T.addEdge(v1, v2, edgeList[i].weight);
				vertexSets.union(r1, r2);
			}
		}
		return T;
	}
}
